package com.demo.java.OD51_100.OD57;

import java.util.HashSet;
import java.util.Objects;
import java.util.Scanner;
import java.util.Set;

/**
 * @author bug菌
 * @Source 公众号：猿圈奇妙屋
 * @des： 【机器人走迷宫】问题
 * @url： https://blog.csdn.net/weixin_43970743/article/details/145600489
 */
public class OdMain {
    // 迷宫的宽度（x方向）和高度（y方向）
    static int xLength;
    static int yLength;

    // 位置类，表示迷宫中的某个点
    static class CheckModel {
        int x;
        int y;

        public CheckModel(int x, int y) {
            this.x = x;
            this.y = y;
        }

        // 重写 hashCode 方法，使得可以正确使用 HashSet
        @Override
        public int hashCode() {
            return Objects.hash(x, y);
        }

        // 重写 equals 方法，确保 HashSet 识别相同坐标的点
        @Override
        public boolean equals(Object o) {
            if (o == this) return true;
            if (o == null || getClass() != o.getClass()) return false;
            CheckModel check = (CheckModel) o;
            return x == check.x && y == check.y;
        }
    }

    /**
     * 递归查找所有可达的位置
     * @param x 当前 x 坐标
     * @param y 当前 y 坐标
     * @param wallSet 墙的集合（不能通行的点）
     * @param checkSet 访问过的点集合
     * @param finishSet 终止的点集合（机器人无法继续前进的点）
     */
    private static void findItOut(int x, int y, Set<CheckModel> wallSet, Set<CheckModel> checkSet,
                                  Set<CheckModel> finishSet) {
        // 如果到达终点（右下角），加入 finishSet
        if (yLength - 1 == y && xLength - 1 == x) {
            finishSet.add(new CheckModel(x, y));
        }

        // 越界检测
        if (yLength <= y || x >= xLength) {
            return;
        }

        // 标记当前位置为已访问
        checkSet.add(new CheckModel(x, y));

        // 向上（北）移动
        if (!wallSet.contains(new CheckModel(x, y + 1))) {
            findItOut(x, y + 1, wallSet, checkSet, finishSet);
        } else {
            // 如果遇到墙，当前点加入 finishSet
            finishSet.add(new CheckModel(x, y));
        }

        // 向右（东）移动
        if (!wallSet.contains(new CheckModel(x + 1, y))) {
            findItOut(x + 1, y, wallSet, checkSet, finishSet);
        } else {
            // 如果遇到墙，当前点加入 finishSet
            finishSet.add(new CheckModel(x, y));
        }
    }

    public static void main(String[] args) {
        try {
            Scanner s = new Scanner(System.in);

            // 读取迷宫的大小（xLength 和 yLength）
            xLength = s.nextInt();
            yLength = s.nextInt();

            // 读取墙的数量
            int size = s.nextInt();
            int[][] values = new int[size][2];

            // 读取墙的坐标
            for (int i = 0; i < size; ++i) {
                values[i][0] = s.nextInt();
                values[i][1] = s.nextInt();
            }

            // 统计陷阱点和无效点
            int trapCount = 0;
            int invalidCount = 0;

            // 记录墙的位置
            Set<CheckModel> wallHashSet = new HashSet<>();
            for (int[] wall : values) {
                wallHashSet.add(new CheckModel(wall[0], wall[1]));
            }

            // 记录访问过的点
            Set<CheckModel> checksHashSet = new HashSet<>();
            // 记录终止的点
            Set<CheckModel> finishHashSet = new HashSet<>();

            // 计算从 (0,0) 开始可到达的所有点
            findItOut(0, 0, wallHashSet, checksHashSet, finishHashSet);

            // 计算无效点：迷宫总点数 - 访问过的点数 - 墙的点数
            invalidCount = xLength * yLength - checksHashSet.size() - wallHashSet.size();

            // 计算陷阱点（无法到达终点的终止点）
            for (CheckModel model : finishHashSet) {
                Set<CheckModel> checksT = new HashSet<>();
                Set<CheckModel> finishT = new HashSet<>();
                findItOut(model.x, model.y, wallHashSet, checksT, finishT);

                // 如果从当前终止点无法到达终点，则为陷阱点
                if (!finishT.contains(new CheckModel(xLength - 1, yLength - 1))) {
                    trapCount++;
                }
            }

            // 输出结果（陷阱点数量和无效点数量）
            System.out.print(trapCount + " " + invalidCount);
        } catch (Exception e) {
            e.printStackTrace();
            System.out.println("input error");
        }
    }
}
